﻿#include<stdio.h>
#include<string.h>
#include<graphics.h>
#include<time.h>
#include<math.h>
#include<easyx.h>
#include <conio.h>

#define WIDTH 1300 //屏幕宽度
#define HEIGHT 800 //屏幕高度
#define BLOCK_WIDTH 20 //单个方块宽度
#define PEROID 200 //间隔时间
#define LENGTH 25 //排序数组长度
#define MAX_NUM 11//生成的最大值
using namespace std;

int array[LENGTH];
int default_array[LENGTH];
int count; //用于计数当前次数
long long countSum; //总操作数
int countTimes = 0; //局数
bool quickPass = 0; //快速跳过

void randArray() { //生成LENGTH长度的随机数组
    time_t t;
    srand((unsigned)time(&t)); //随机数发生器
    for (int i = 0; i < LENGTH; i++) {
        array[i] = (rand() % (MAX_NUM + 1)) + 1;
        default_array[i] = array[i];
    }
}

void reset() {
    for (int i = 0; i < LENGTH; i++) {
        array[i] = default_array[i];
    }
}

COLORREF findColor(int i) {
    if(i == 1) return RGB(255, 0, 0);
    if (i == 2) return RGB(0, 255, 0);
    if (i == 3) return RGB(0, 0, 255);
}

void show(int l, int r, int h) {
    cleardevice();
    BeginBatchDraw();
    TCHAR text[100];
    _stprintf_s(text, _T("是否开启快速模式:"));
    outtextxy(600, HEIGHT - 30, text);
    _stprintf_s(text, _T("工作原理:"));
    outtextxy(600, 20, text);
    _stprintf_s(text, _T("排序对不相邻的记录进行比较和移动："));
    outtextxy(600, 40, text);
    _stprintf_s(text, _T("1.将待排序序列分为若干子序列（每个子序列的元素在原始数组中间距相同）；"));
    outtextxy(600, 60, text);
    _stprintf_s(text, _T("2.对这些子序列进行插入排序；"));
    outtextxy(600, 80, text);
    _stprintf_s(text, _T("3.减小每个子序列中元素之间的间距(本示例中使用除以3)，重复上述过程直至间距减少为 1。"));
    outtextxy(600, 100, text);
    _stprintf_s(text, _T("支持的操作:"));
    outtextxy(600, 130, text);
    _stprintf_s(text, _T("1.结束时按下 Q 切换快速模式(跳过过程直接出结果，可快速测试平均次数);"));
    outtextxy(600, 150, text);
    _stprintf_s(text, _T("2.结束时按下 R 再次重复之前的排序过程;"));
    outtextxy(600, 170, text);
    _stprintf_s(text, _T("3.结束时按下 F 重新生成数据并排序;"));
    outtextxy(600, 190, text);
    _stprintf_s(text, _T("上方数字解释:"));
    outtextxy(600, 220, text);
    _stprintf_s(text, _T("从左到右依次为: 当前间距, 测试数组长度, 每次排序平均次数, 当前次数， 总局数"));
    outtextxy(600, 240, text);
    TCHAR s[5];
    _stprintf_s(s, _T("%d"), h);		
    outtextxy(20, 20, s);
    _stprintf_s(s, _T("%d"), LENGTH);		
    outtextxy(40, 20, s);
    _stprintf_s(s, _T("%d"), countSum / countTimes);	
    outtextxy(70, 20, s);
    _stprintf_s(s, _T("%d"), count);
    outtextxy(100, 20, s);
    _stprintf_s(s, _T("%d"), countTimes);
    outtextxy(130, 20, s);
    _stprintf_s(s, _T("%d"), quickPass);
    outtextxy(750, HEIGHT - 30, s);
    for (int i = 0; i < LENGTH; i++) {
        setfillcolor(findColor(1));
        if(i == l) setfillcolor(findColor(2));
        if(i == r) setfillcolor(findColor(3));
        fillrectangle(60 + BLOCK_WIDTH * i, HEIGHT, 60 + BLOCK_WIDTH * (i+1), HEIGHT - (array[i] * 50));
    }
    FlushBatchDraw();
    EndBatchDraw();
    if(!quickPass) Sleep(PEROID);
}

int main()
{
    initgraph(WIDTH, HEIGHT);
    setbkcolor(BLACK);
    randArray();
    while (1) {
        int h = 1;
        countTimes++;
        count = 0;
        while (h < LENGTH / 3) {
            h = 3 * h + 1;
        }
        while (h >= 1) {
            for (int i = h; i < LENGTH; i++) {
                for (int j = i; j >= h; j -= h) {
                    count++; countSum++;
                    show(j, j - h, h);
                    if (array[j] < array[j - h]) {
                        int temp = array[j];
                        array[j] = array[j - h];
                        array[j - h] = temp;
                    }
                    else {
                        show(j, j - h, h);
                        break;
                    }
                    show(j - h, j, h);
                }
            }
            h = h / 3;
        }
        while (1) {
            show(-1, -1, h);
            if (_kbhit) {
                char val = _getch();
                if (val == 'r') {
                    reset();
                    break;
                }
                if (val == 'f') {
                    randArray();
                    break;
                }
                if (val == 'q') {
                    if (quickPass) {
                        quickPass = 0;
                    } else {
                        quickPass = 1;
                    }
                }
            }
        };
    }
    return 0;
}